The present invention is related to wireless networks, and in particular to a spanning tree protocol for use with an ad-hoc wireless network to avoid loops in the wireless network.
In the area of local area networks (LANs), and in particular, LAN bridges, spanning tree protocols are known for preventing loops in a bridged (typically wired) network. In particular, the Institute of Electrical and Electronics Engineers (IEEE) has developed a network communication standard IEEE 802.1d entitled, “Media Access Control (MAC) Bridges,” originally approved May 31, 1990 (hereinafter “IEEE 802.1d”), and also high-speed (IEEE 802.1w) and high-density (IEEE 802.1s) counterparts. IEEE 802.1d includes a supplement 802.1r—“GARP Proprietary Attribute Registration Protocol (GPRP)” that defines an additional GARP Application aimed at allowing vendor-specific attribute values to be distributed via GARP in a standard and interoperable manner, and allowing vendor-specific attribute values that may have a wider application within other vendors equipment to be made available for more general use. Any of these protocols, and also a collection of these standard protocols is referred to herein as a or the “standard IEEE 802.1 spanning tree protocol,” also “standard IEEE 802.1 STP” In brief, the standard IEEE 802.1 protocol describes functions to be performed by a compliant bridge including maintaining the spanning tree topology for the bridge, building and maintenance of a filtering database, relaying and filtering of frames, and transmission of Bridge Protocol Data Units (BPDUs). A BPDU is a special message that bridges transmit to each other to facilitate determination of a spanning tree topology.
Wireless networks are becoming widespread. For example, wireless local area networks (WLANs) that conform to the IEEE 802.11 standard are becoming more and more popular. One way of operating a WLAN is in infrastructure mode according to which some wireless stations operate as access points, and each access point has client stations. All communication from and to a client station is via its access point. WLANS may also operate in ad-hoc mode according to which any station may communicate directly with any other station. Such a wireless network forms a mesh. The present invention is particularly applicable to such mesh wireless networks where, as in a wired mesh, any station could have a wireless link to another station. Such a network is also called a multi-hop wireless network herein.
As in the case of wired networks, it is desirable to avoid forming loops in a multi-hop wireless network. Special purpose protocols that provide similar functionality to the standard IEEE 801.1 spanning tree protocols have been designed. However, there is a desire in the art for working with standard IEEE 802.1 protocols in order to maintain compatibility.
There is therefore a need in the art for combining the process of establishing a radio link in a wireless network with standard IEEE 802.1 spanning tree protocols to decide which links to establish in order to avoid undesirable loops.
The standard IEEE 802.1 spanning tree protocol was originally designed to work over wired Ethernet links and cannot operate until the low-level links are established. In wireless networks such as IEEE 802.11 networks, low-level link establishment is a multi-step process. The blocking/tearing down of established links by a spanning tree process such as used in a wired network may be undesirable. Thus, the standard IEEE 802.1 spanning tree protocol as designed cannot simply operate in a wireless network environment.
Some other limitations in the standard IEEE 802.1 spanning tree protocol when used for multi-hop IEEE 802.11 conforming wireless networks include:                A typical standard IEEE 802.1 spanning tree protocol chooses a root bridge, and further chooses one link over another based on such parameters as the switch-id, the port-id, the bridge-priority, the port-priority and the path cost to the root according to some cost measure. These parameters and path cost calculations based on link speeds, being designed with wired networks in mind, have limited usefulness for radio links. Radio links, on the other hand, have radio link parameters associated therewith, including the radio path loss, the received signal strength, the received signal quality, e.g., as measured by a measure of the EVM of a received signal, and so forth, that are relevant in determining link quality, and thus, that should play a part in selecting paths.        Because of factors such as interference, path loss, multipath fading, and so forth, radio inks, e.g., IEEE 802.11 links are much more likely to temporarily go down than are wired links. There is no provision in the IEEE 802.1 spanning tree protocol for links that temporarily go down.        Spanning tree protocols for wired networks provides path redundancy using alternate and/or backup links. Maintaining such redundant links in wireless networks, e.g., IEEE 802.11 networks, may result in inefficient usage of the available bandwidth. Maintaining such links may further add unacceptable overhead.        Spanning tree protocol for wired networks are designed for fixed Ethernet LANs. Radio links, e.g., Multi-hop wireless mesh networks, such as IEEE 802.11 conforming networks may be mobile in an unpredictable random-like manner.        
Thus, there is a need in the art for a WSTP wireless spanning tree protocol that includes a root bridge selection method that incorporate radio parameters, and that otherwise operates substantially as a standard IEEE 802.1 spanning tree protocol.
Prior art in the field of ad-hoc wireless networks includes work on mobility protocols, such as Mobile-IP and on Ad-hoc routing for establishing loop-free topologies in mobile/multihop wireless networks. Note that mobile ad-hoc networks are often referred to as MANETs (Mobile Ad-hoc NETworks) in the literature. For a routing method, see, for example, Elizabeth Royer and C-K Toh “A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks,” IEEE Personal Communications Magazine, April 1999, pp. 46-55.
Implementations of the IEEE 802.1 spanning tree algorithms are common. It is desirable to not have to modify existing protocol stacks at end stations. Furthermore, it is desirable to not have to modify existing protocol stacks, such as mobile in ad-hoc mobile protocols (MANET protocols) and L3 routing logic in intermediate devices, common in Mobile-IP protocols.
It further is desirable to have a wireless spanning tree algorithm that avoids temporary loops. Temporary loops can be a problem in a bridged, multi-hop wireless network, often resulting in dramatically rapid packet proliferation through the network.
There still is a need in the art for extending spanning tree protocols for ad-hoc wireless networks, in particular, for IEEE 802.11 networks.